package 剑指offer;

public class Coin {
    static int[] arr = {1, 5, 17, 21, 65, 69, 81, 85};
    static String[] strs = new String[arr.length];

    public static void main(String[] args) {

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "=");

            System.out.println("-------" + getCoin(arr[i], i));

            System.out.println(strs[i]);
            System.out.println("------------**********---------------");
        }

    }

    public static int getCoinF(int num) {
        if (num == 1024) {
            return 0;
        }
        int leftCoin = 1024 - num;
        int count = 0;
        int temp = 64;
        while (leftCoin != 0) {
            count += leftCoin / temp;
            leftCoin = leftCoin % temp;
            temp /= 4;
        }
        return count;
    }

    public static int getCoin(int num, int i) {
        if (num == 1024) {
            return 0;
        }
        int count = 0;
        int remain = num;
        int coin64 = remain / 64;
        int coin16 = remain / 16;
        int coin4 = remain / 4;
        int coin1 = remain / 1;
        if (coin64 == 0) {
            if (coin16 == 0) {
                if (coin4 == 0) {
                    count = coin1;
                } else {
                    coin1 = remain % 4;
                    count = coin4 + remain % 4;
                }
            } else {
                int temp = remain;
                remain = remain % 16;
                coin4 = remain / 4;
                if (coin4 == 0) {
                    coin1 = temp % 16;
                    coin16 = remain / 16;
                    count = coin16 + temp % 16;
                } else {
                    coin1 = remain % 4;
                    count = coin16 + coin4 + remain % 4;
                }
            }

        } else {
            int temp = remain;
            remain = remain % 64;
            coin16 = remain / 16;
            coin4 = remain / 4;
            if (coin16 == 0) {
                if (coin4 == 0) {
                    coin1 = temp % 64;
                    count = coin64 + temp % 64;
                } else {
                    coin1 = remain % 4;

                    count = coin64 + coin4 + remain % 4;
                }
            } else {
                remain = remain % 16;
                coin4 = remain / 4;
                if (coin4 == 0) {
                    coin1 = temp % 16;
                    count = coin64 + coin16 + temp % 16;
                } else {
                    coin1 = remain % 4;
                    count = coin64 + coin16 + coin4 + remain % 4;
                }
            }
        }
        strs[i] = "64*" + coin64 + "+16*" + coin16 + "+4*" + coin4 + "+1*" + coin1;
        return count;
    }
}
